// 回文链表

package Leetcode;

class Solution_234 {
    public boolean isPalindrome(ListNode head) {
        int length = 0;
        ListNode cur = head;
        while (cur != null) {
            length++;
            cur = cur.next;
        }
        if (length <= 1)
            return true;

        // 翻转一半的链表
        int half = (length + 1) / 2;
        cur = head;
        for (int k = 0; k < half - 1; k++) { // 指针移动到一半的位置
            cur = cur.next;
        }
        // 使用双指针进行翻转
        ListNode pre = cur;
        cur = cur.next;
        while (cur != null) {
            ListNode n = cur.next;
            cur.next = pre;
            pre = cur;
            if (n == null)
                break;
            cur = n;
        }
        for (int i = 0; i < half; i++) {
            if (head.val != cur.val)
                return false;
            head = head.next;
            cur = cur.next;
        }
        return true;
    }
}